package leetcode每日一题;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * 1. 问题描述
 *      对于非负整数X而言，X的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果X = 1231，那么其数组形式为[1,2,3,1]。
 *      给定非负整数 X 的数组形式A，返回整数X+K的数组形式。
 *
 * 2. 算法分析
 *      双指针法
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 数组形式的整数的加法 {
    public static void main(String[] args) {

    }

    public static List<Integer> addToArrayForm1(int[] A, int K) {
        Stack<Integer> stack = new Stack<>();
        while(K >= 10) {
            stack.add(K % 10);
            K /= 10;
        }
        stack.add(K);
        // 此时stack的出栈顺序就是K数字的从高到低位的顺序
        // 将stack转化为数组
        int[] B = new int[stack.size()]; int index = 0;
        while(!stack.isEmpty()) {
            B[index] = stack.pop();
            index++;
        }
        // 定义双指针
        int i = A.length - 1;
        int j = B.length - 1;
        int reminder = 0;
        int next = 0;
        Stack<Integer> tmp = new Stack<>();
        while(i >= 0 && j >= 0) {
            reminder = (A[i] + B[j] + next) % 10;
            next = (A[i] + B[j] + next) / 10;
            tmp.add(reminder);
            i--;
            j--;
        }
        if(i == -1 && j == -1) {
            if(next != 0) {
                tmp.add(next);
            }
        }
        if(i >= 0 && j == -1) {
            for(int s = i; s >= 0; s--) {
                tmp.add((A[s] + next) % 10);
                next = (A[s] + next) / 10;
            }
            if(next != 0) {
                tmp.add(next);
            }
        }
        if(j >= 0 && i == -1) {
            for(int s = j; s >= 0; s--) {
                tmp.add((B[s] + next) % 10);
                next = (B[s] + next) / 10;
            }
            if(next != 0) {
                tmp.add(next);
            }
        }
        List<Integer> res = new ArrayList<>();
        while(!tmp.isEmpty()) {
            res.add(tmp.pop());
        }
        return res;
    }


    public List<Integer> addToArrayForm2(int[] A, int K) {
        List<Integer> res = new ArrayList<Integer>();
        int n = A.length;
        for(int i = n - 1; i >= 0; i--) {
            int sum = A[i] + K;
            res.add(sum % 10);
            K = sum / 10;
        }
        while(K >= 10) {
            res.add(K % 10);
            K /= 10;
        }
        if(K != 0) {
            res.add(K);
        }
        Collections.reverse(res);
        return res;
    }
}
